State Machines
State machines are sequential logic systems whose output signals are a function of previous and present input signals, in contrast to combinatorial logic systems whose output signals are a function of present input signals alone. State machines typically include one or more storage elements and occupy a plurality of states which are determined by input signals and the contents of the one or more storage elements. State machines "move" sequentially between the states (that is, one state becomes inactive and another state becomes active) in response to the input signals and transition rules established by combinatorial logic, which defines a logic "path" between the states. State machines are typically incorporated into circuits which also include other combinatorial logic and sequential logic circuitry, and frequently serve as controllers.
FIG. 1 shows a bubble flow diagram of a state machine which includes seven states, STATE 1 to STATE 7. The state machine receives input signals A through E. As indicated in FIG. 1, the state machine remains in STATE 1 until one of two transition rules is satisfied: (1) if input signal A is high, B is high, and C is low, the state machine moves into STATE 4; (2) if input signal A is high, B is low and C is high, the state machine moves into STATE 2. Similarly, the state machine remains in STATE 4 until input signal A is high, B is high and C is low. From STATE 2, the state machine enters STATE 3 if input signal D is high, or enters STATE 4 if input signal D is low. The other transition rules resulting in movements between states are also indicated.
State machines are commonly implemented in programmable logic devices. Programmable logic devices include programmable array logic devices (PALs) and field programmable gate arrays (FPGAs).
The state of a typical state machine is defined by the states (high or low output signals) of a set of flip-flops which are part of the state machine. In PALs, which have wide combinatorial logic circuitry but relatively few flip-flops, state machines are typically implemented using a highly encoded system wherein the output signals of all of the flip-flops define the active state of the state machine. For example, four flip-flops are used to define 16 separate states of a 16-state machine. Another scheme, call one-hot encoding (OHE), is frequently used to implement state machines in FPGAs, which contain numerous flip-flops but limited fan-in capability. In OHE, each state is represented by a single flip-flop. Thus, 16 flips are used to define 16 separate states. As suggested by the name OHE, only one flip-flop associated with the state machine need be in a logical "1" (hot) state to represent the active state of the state machine. OHE requires a larger number of flip-flops than are required in the highly encoded systems implemented in PAL devices, but offers higher performance (speed) because there are fewer levels of logic between the flip-flops.
Design Entry Methods
Circuit design engineers typically employ one or more computer-aided engineering (CAE) software programs to generate and test their circuit designs. Circuit designs are entered into computer memory using one of several design entry methods. Typical CAE programs include some form of netlist generator for producing netlists from circuit designs. A netlist is a listing of the components and interconnections of the circuit design which is usable either to produce a custom IC or to configure a programmable logic device.
The design entry methods used for entering circuit designs into computer memory include equations, truth tables, waveforms (timing diagrams), schematic diagrams, state (flow) diagrams and hardware description languages. Equations are groups of Boolean logic equations which describe the logic functions of a circuit. Truth tables are tabulations indicating the relation of all output logic levels of a circuit to all possible combinations of input logic levels. Waveforms or timing diagrams are graphical representations of the relationships between input signals and corresponding output signals of a circuit. Schematic diagrams are descriptions of the physical components and interconnections of a circuit. Finally, flow diagrams ("flowcharts") are functional descriptions of the logic functions of a circuit.
Schematic Diagrams
Schematic diagrams are considered by many circuit designers to be the most intuitive method of circuit design entry. Schematic diagram software programs (referred to herein as "schematic capture packages") allow a circuit design to be entered into computer memory in the form of schematic diagram comprising circuit component symbols connected by signal paths (interconnection lines). A circuit designer can "read" a schematic diagram displayed on a video screen and understand the interrelationships of the circuit components without a specialized knowledge of the schematic capture package.
As shown in FIG. 2, a schematic capture package 1000 typically includes several software tools including a component generator 1010, a schematic editor 1020, a display generator 1030 and a netlist generator 1040. A netlist is a computer memory file including a list of components (logic gates, flip flops, etc.) and interconnections between the components which represent a circuit design. The component generator 1010 allows a user to define and store schematic components in a schematic component library 1015. A schematic component is comprised of two parts: a schematic symbol which is displayed on a video monitor, and an underlying circuit design which defines the function of the schematic component. Schematic components are recognized by the schematic capture package as representing the functions of their underlying circuit designs. After a schematic component library 1015 is generated, the schematic editor 1020 is used to copy schematic components from the library and to connect the schematic components to form a circuit design which is stored in a schematic diagram file 1025. During the process of forming a schematic diagram, the display generator 1030 reads the schematic diagram file 1025 and generates a schematic diagram on a video display 1035. After completion of the schematic diagram, the netlist generator 1040 reads the schematic diagram file 1025 and converts the circuit design into a netlist 1050. Netlist 1040 differs from schematic diagram 1025 in form. The schematic diagram is a graphical illustration easily recognized by a user, while the netlist is a list of components and the lines which interconnect them, and is easily manipulated by a computer.
FIGS. 3(a) to 3(d) are provided to illustrate how the component generator 1010 (FIG. 2) is used to simplify the production of schematic diagrams. FIG. 3(a) shows a low-level schematic diagram of a multiplexer (MUX). The low-level schematic diagram is drawn at the "transistor level"; that is, the schematic diagram is comprised of individual logic element symbols representing discrete transistors. FIG. 3(b) shows a middle-level schematic diagram of the MUX. The middle-level diagram is drawn at the "gate level"; that is, related groups of transistors are represented by symbols commonly recognized by circuit designers as AND gates 1110 and 1120, and an OR gate 1130. Note that the input signals IN1 and IN2, the select signal SEL and the output signal OUT of the low-level diagram of FIG. 3(a) are identified in the middle-level diagram of FIG. 3(b). FIG. 3(c) shows a high-level symbol 1150 representing the MUX of FIGS. 11(a) and 11(b). The high-level symbol 1150 represents the MUX as a trapezoid having input terminals IN1, IN2, SEL and OUT. When the high-level symbol 1150 is entered into a schematic diagram, as shown in FIG. 3(d), the high-level symbol 1150 will be recognized by a schematic capture package as being comprised of the circuit shown in FIG. 3(a).
The process of defining high-level components in terms of lower-level schematic diagrams using the component generator 1010 (FIG. 2) is known as "hierarchy". Hierarchy greatly reduces the time necessary to generate a circuit diagram because it allows the circuit designer a short-hand method of entering commonly-known or repeatedly-used circuit structures. Further, the higher-level symbols, such as the MUX symbol of FIG. 3(c), are well known; therefore, circuit designers need not design at the transistor level, which is time-consuming and tedious. Schematic capture programs typically provide a library of commonly-used schematic components. In addition, schematic component libraries are provided by programmable logic device manufacturers. Also, a library may be supplemented by schematic components generated by the user.
The schematic editor 1020 of a schematic capture package 1000 is a user's schematic diagram production tool. With the schematic editor 1020, the user accesses the schematic component library 1040 and copies the schematic components into a schematic diagram file 1025. The user draws signal lines between the input and output terminals of the schematic components to produce a representation of a desired circuit design. As the user enters the schematic components and interconnecting lines into computer memory, the computer generates a graphic representation of the schematic diagram on a video display terminal 1035 in which the symbols representing the schematic components are shown along with interconnection lines representing conductive signal paths for transmitting signals between the schematic components. The user "reads" the displayed schematic diagram by looking at the signal paths and schematic components shown on display terminal 1035. The user then modifies or adjusts the circuit design by modifying the schematic diagram file 1025 based on feedback provided from display terminal 1035.
Finally, after a user is satisfied with having entered a circuit design into the computer using the schematic editor 1020, the netlist generator 1030 reads the schematic diagram file 1025 and converts the circuit design into a netlist 1050.
A presently available schematic capture package is Workview.TM., which is available from ViewLogic Systems, Inc., having a principle place of business at Marlboro, Mass.
A disadvantage of prior art schematic capture packages is that when a circuit design includes a state machine, the schematic diagram of the state machine, which must be entered by the user, typically fails to intuitively present the logic defining the state machine.
Flow Diagrams
Flow diagrams (flowcharts) are considered by many circuit designers to be the most intuitive design entry method for entering state machine descriptions into computer memory. Flow diagrams are graphical and/or text based descriptions which illustrate the paths between the states of a state machine.
FIG. 4 shows an example of a flow diagram of a four-state machine. In FIG. 4, the rounded rectangles 41 through 44 indicate individual states and the diamonds 45, 46 indicate decision branches controlled by test signals (not shown). Linking the states and decision branches are arrows 51 through 56 indicating flow paths. The state machine moves from state to state along the flow paths as directed by the decision branches of the flow diagram.
Kobayashi et al. U.S. Pat. No. 4,922,432 teaches a CAE flow diagram program which allows a circuit designer to enter a state machine as a flow diagram comprised of blocks representing states, diamonds representing decision branches, and arrows indicating the logic paths linking the states and decision branches. Associated with one or more of the states is a textual description of logic controlled by that state. In addition, each decision branch identifies a logic equation stored in memory.
However, Kobayashi et al. does not display the combinatorial and sequential logic circuitry which is associated with the state machine. That is, although a user can understand the logic of the state machine, the user cannot easily understand the relationships between the state machine and the related circuit design. Specifically, for applications in which the state machine is a small part of the overall circuit design, it can be difficult for the circuit designer to comprehend the overall circuit design.
Another disadvantage of the above-mentioned flow diagram program is that it requires a user to learn a new design entry format which is incompatible with a schematic capture package. Circuit designers who are familiar with schematic capture packages may find the new format difficult to learn. Further, because the flow diagram program is incompatible with schematic capture packages, a user must purchase both the flow diagram program and a schematic capture package in order to enter circuit designs in both the schematic diagram format and the flow diagram format. These programs are typically expensive.